Единичный прямоугольник

Ограничение времени1 секунда
Ограничение памяти256 Мб
Вводстандартный ввод или input.txt
Выводстандартный вывод или output.txt

Дана таблица размером N × M N \times M , состоящая из нулей и единиц. Вам необходимо ответить на Q Q запросов. Каждый запрос представляет собой два целых числа W W и H H . Требуется определить, существует ли в данной таблице прямоугольник, полностью состоящий из единиц, шириной ровно W W и высотой ровно H H . Стороны прямоугольника должны быть параллельны сторонам таблицы.

Формат ввода

В первой строке через пробел вводятся три целых числа: N , M , Q N, M, Q ( 1 ≤ N , M ≤ 1 06 , N ⋅ M ≤ 1 06 , 1 ≤ Q ≤ 1 05 1 \le N, M \le 10^6, N \cdot M \le 10^6, 1 \le Q \le 10^5 ).

В следующих N N строках вводится сама таблица.

Каждая строка содержит M M символов ('0' или '1') без пробелов. В следующих Q Q строках вводятся пары целых чисел W W и H H ( 1 ≤ W ≤ M , 1 ≤ H ≤ N 1 \le W \le M, 1 \le H \le N ).

Формат вывода

Если введено недопустимое значение n — выведите -2.
Для каждого запроса выведите в отдельной строке "YES", если такой прямоугольник существует, и "NO" в противном случае.

Система оценивания

Решения, верно работающие при n , m , q ≤ 10 n, m, q \le 10 будут получать не менее 20 20 баллов.

Решения верно работающие при n ⋅ m ≤ 1 06 , q ≤ 100 n \cdot m \le 10^6, q \le 100 будут получать не менее 50 50 баллов.

Решения, верно работающие при n ⋅ m ≤ 1 06 n \cdot m \le 10^6 , U n i q u e ( w ) ≤ 20 Unique(w) \le 20 будут получать не менее 20 20 баллов, где U n i q u e ( w ) Unique(w) , кол-во различных широт в запросах.

Пример 1

ВводВывод
3 4 2
1110
1110
0000
3 2
3 3

YES
NO

Пример 2

ВводВывод
4 2 3
11
10
11
11
1 4
2 1
2 2

YES
YES
YES